package 二叉树.树基本知识与重建;

/**
 * Created by Administrator on 2017/8/21.
 */
//题目描述
//        输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**
 public class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
 this.val = val;

 }

 }
 */
/*思路：参考剑指offer(作者原版)
1、首先设置标志位result = false，因为一旦匹配成功result就设为true，
剩下的代码不会执行，如果匹配不成功，默认返回false
2、递归思想，如果根节点相同则递归调用DoesTree1HaveTree2（），
如果根节点不相同，则判断tree1的左子树和tree2是否相同，
再判断右子树和tree2是否相同
3、注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断，
DoesTree1HasTree2中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功，
tree1为空有两种情况（1）如果tree1为空&&tree2不为空说明不匹配，
（2）如果tree1为空，tree2为空，说明匹配。

*/
public class HasSubtree {
    public boolean hasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false; //默认标志，一旦匹配成功result就设为true
        if(root1 != null && root2 != null){ //因为题目规定了两棵树只要有一个null，即返回false
            if(root1.val == root2.val){ //判断根节点处值及后面左右的值是否相同
                result = doesTree1HaveTree2(root1,root2);
            }
            if(!result){result = hasSubtree(root1.left, root2);} //这个跟没有匹配上，那么接着匹配跟的左子树
            if(!result){result = hasSubtree(root1.right, root2);}//这个跟没有匹配上，那么接着匹配跟的左子树
        }
        return result;
    }
    public boolean doesTree1HaveTree2(TreeNode root1,TreeNode root2){
        if(root1 == null && root2 != null) return false; //说明父树A的高度小于子树B的高度，那么B肯定不是A的子结构
        if(root2 == null) return true; //说明父树A的高度大于等于子树B的高度均可，这是因为前面一直是匹配的，所以可以在叶子层返回true了
        if(root1.val != root2.val) return false; //比较的值不一样，立即结束
        return doesTree1HaveTree2(root1.left, root2.left) && doesTree1HaveTree2(root1.right, root2.right); //判断左右子树是否一样的值
    }












    //我的重写
    //现在当前根节点处判断，在去左右子树根节点处判断
    public boolean _hasSubtree(TreeNode A,TreeNode B){
        boolean flag=false; //默认返回
        if(A!=null&&B!=null){ //注意到A、B==null的情况全部返回默认的false
            flag=doesAHaveSubtreeB(A,B);
            //当前节点为根的不能匹配时，寻找下面的左右子树
            if(!flag) doesAHaveSubtreeB(A.left,B);
            if(!flag) doesAHaveSubtreeB(A.right,B);
        }
        return flag;
    }

    private boolean doesAHaveSubtreeB(TreeNode A, TreeNode B) {
        //意外情况排除
        //1、A树的高度小于B树的高度
        if(A==null&&B!=null) return false;
        //2、A树的高度大于等于B树的高度(此时，A!=意味着A树高度大于B树，A==意味着A树高度等于B树)
        if(B==null) return true;
        //3、节点处的值不一样
        if(A.val!=B.val) return false;

        //充分利用短路的特点，只有有一个节点为false，那后面的就不需要判断了，B肯定不是A的子树
        return doesAHaveSubtreeB(A.left,B.left)&&doesAHaveSubtreeB(A.right,B.right);//判断每个节点是否一样
    }
}
